#include<iostream>
#include<vector>
using namespace std;
bool searchMatrix(vector<vector<int>>& matrix, int target)
{
    int min = 0;
    int max = matrix.size()-1;
    int position = 0;
    while(min<=max)
    {
        int mid = ((max - min)>>1) + min;
        //寻找第一个比目标元素大的首个行元素
        if(matrix[mid][0] > target)
        {
            max = mid - 1;
        }else{
            position = mid;
            min = mid + 1;
        }
        // cout<<"circle:"<<mid<<" ";
    }
    //cout<<"position is:"<<position<<endl;
    //确定第一个比目标元素大的行之后，在行中寻找是否有目标元素
    min = 0;
    max = matrix[position].size()-1;
    while(min<=max)
    {
        int mid = ((max - min)>>1) + min;
        if(matrix[position][mid] == target)
        {
            return true;
        }else if(matrix[position][mid] > target)
        {
            max = mid - 1;
        }else{
            min = mid + 1;
        }
    }
    return false;
}
int main()
{
    vector<vector<int>> v(3,vector<int>(4));
    cout<<"Enter the elements of the matrix:"<<endl;
    for(int i=0;i<v.size();i++)
    {
        for(int j=0;j<v[i].size();j++)
        {
            cin>>v[i][j];
        }
    }
    cout<<"The matrix is:"<<endl;
    for(int i=0;i<v.size();i++)
    {
        for(int j=0;j<v[i].size();j++)
        {
            cout<<v[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<"target element is:"<<endl;
    int target;
    cin>>target;
    if(searchMatrix(v, target)){
        cout<<"The target element is in the matrix."<<endl;
    }else
    {
        cout<<"The target element is not in the matrix."<<endl;
    }
    return 0;
}